#include <iostream>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

void insertTailList(ListNode *head, int val)
{
    //尾插法
    while (head->next)  //走到链表的末尾来插入
        head = head->next; 
    
    ListNode *cur = new ListNode(-1);
    cur->val = val;
    head->next = cur;
    cur->next = NULL;
}

void insertHeadList(ListNode *head, int val)
{
    //头插法
    ListNode *cur = new ListNode(-1);
    cur->val = val;
    cur->next = head->next;
    head->next = cur;
}

void travereList(ListNode *head)
{
    head = head->next;
    while (head)
    {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int lenList(ListNode *head)
{
    int len = 0;
    head = head->next;
    while (head)
    {
        len++;
        head = head->next;
    }
    return len;
}

ListNode *searchList(ListNode *head, int fdata)
{
    head = head->next;
    while (head)
    {
        if (head->val == fdata)
            return head;
        head = head->next;
    }
    return NULL;
}

void deleteNode(ListNode *head, ListNode *fnode)
{
    ListNode *t = head;

    if (fnode->next == NULL)
    {
        //该结点为最后一个结点 找到该结点的前一个结点 将其next指向为NULL即可
        while (head->next != fnode)
            head = head->next;
        head->next = NULL;
        free(fnode);
    }
    else
    {
        // 非尾结点  将fnode下一个结点的数值赋给fnode结点，删除下一个结点即可，最快捷
        ListNode *t = fnode->next;
        fnode->val = t->val;
        fnode->next = t->next;
    }
}

void sortList(ListNode *head)
{
    ListNode *p, *q, *pre;
    int len = lenList(head);
    for (int i = 0; i < len - 1; i++)
    {
        pre = head; //深刻理解pop的过程
        p = pre->next;
        q = p->next;
        for (int j = 0; j < len - 1 - i; j++)
        {
            if (p->val > q->val)
            {
                pre->next = q;
                p->next = q->next;
                q->next = p;
            }
            pre = pre->next;
            p = pre->next;
            q = p->next;
        }
    }
}

void reverseList(ListNode *head)
{
    ListNode *h = head->next;
    ListNode *temp;
    head->next = NULL;

    while (h)
    {
        temp = h->next;
        h->next = head->next;
        head->next = h;
        h = temp;
    }
}

int main()
{

    ListNode *head;
    int len = 5;

    for (int i = 0; i < len; i++)
    {
        insertTailList(head, i + 1);
    }

    travereList(head);

    reverseList(head);

    travereList(head);

    cout<<lenList(head)<<endl;
    
    return 0;
}
